The invention is related generally to electronic circuits, and more particularly to a parity-sensitive Viterbi detector and technique for recovering information from a read signal. In one embodiment, the Viterbi detector is parity sensitive, and recovers only data sequences having the correct parity. Such parity checking allows the Viterbi detector to more accurately recover information from a read signal having a reduced signal-to-noise ratio (SNR). By allowing the read signal to have a reduced SNR, the Viterbi detector allows one to increase the area density (number of storage locations per square inch) of a storage disk.
The storage capacity of a magnet disk is typically limited by the disk surface area and the minimum read-signal SNR specified for the data recovery circuit . Specifically, the diameter of the disk, and thus the disk surface area, are typically constrained to industry-standard sizes. Therefore, the option of increasing the surface area of the disk to increase the disk""s storage capacity is usually unavailable to disk-drive manufacturers. Furthermore, the SNR of the read signal is a function of the data-storage density on the surface or surfaces of the disk; the higher the storage density, the lower the SNR of the read signal, and vice-versa. Typically, as the SNR of the read signal decreases, the number of read errors that the recovery circuit introduces into the recovered data increases. Unfortunately, an increase in the number of read errors may degrade the effective data-recovery speed of a disk drive to unacceptable levels.
FIG. 1 is a circuit block diagram of part of a conventional disk drive 10, which includes a magnetic storage disk 12 and a read channel 14 for reading data from the disk 12. The read channel 14 includes a read head 16 for sensing the data stored on the disk 12 and for generating a corresponding read signal. A read circuit 18 amplifies and samples the read signal and digitizes the samples, and a digital Viterbi detector 20 recovers the stored data from the digitized samples.
Typically, the greater the data-storage density of the disk 12, the greater the noise the read head 16 picks up while reading the stored data, and thus the lower the SNR of the read signal. The disk 12 typically has a number of concentric data tracks (not shown in FIG. 1) that each have a respective number of data-storage locations. The storage density of the disk 12 is a function of the distances between storage locations along the circumferences of the respective tracks and the distances between respective tracks. The smaller these distances, the higher the storage density, and thus the closer the surrounding storage locations to the read head 16 when it is reading the surrounded location. The closer the surrounding locations to the read head 16, the greater the magnitudes of the magnetic fields that these locations respectively generate at the head 16, and thus the greater the Inter Symbol Interference (ISI). The greater the ISI, the smaller the root-mean-square (rms) amplitude of the read signal. In addition, as the storage density increases, the media noise increases. Generally, the media noise results from the uncertainty in the shapes of the read pulses that constitute the read signal. This uncertainty is caused by unpredictable variations in the positions of the data storage locations from one data-write cycle to the next. Moreover, for a given disk spin rate, as the linear storage density along the tracks increases, the bandwidth of the read head 16 must also increase. This increase in bandwidth causes an increase in the white noise generated by the read head 16. The SNR of the read signal for a particular storage location is the ratio of the rms amplitude of the corresponding read pulse to the sum of the amplitudes of the corresponding media and white noise. Thus, the lower the rms amplitudes of the read pulses and the greater the amplitudes of the media and/or white noise, the lower the SNR of the read signal.
Unfortunately, the Viterbi detector 20 often requires the read signal from the head 16 to have a minimum SNR, and thus often limits the data-storage density of the disk 12. Typically, the accuracy of the detector 20 decreases as the SNR of the read signal decreases. As the accuracy of the detector 20 decreases, the number and severity of read errors, and thus the time needed to correct these errors, increases. Specifically, during operation of the read channel 14, if the error processing circuit (not shown) initially detects a read error, then it tries to correct the error using conventional error-correction techniques. If the processing circuit cannot correct the error using these techniques, then it instructs the read channel 14 to re-read the data from the disk 12. The time needed by the processing circuit for error detection and error correction and the time needed by the read channel 14 for data re-read increase as the number and severity of the read errors increase. As the error-processing and data re-read times increase, the effective data-read speed of the channel 14, and thus of the disk drive 10, decreases. Therefore, to maintain an acceptable effective data-read speed, the read channel 14 is rated for a minimum read-signal SNR. Unfortunately, if one decreases the SNR of the read signal below this minimum, then the accuracy of the read channel 14 degrades such that at best, the effective data-read speed of the disk drive 10 falls below its maximum rated speed, and at worst, the disk drive 10 cannot accurately read the stored data.
To help the reader more easily understand the concepts discussed above and the concepts discussed below in the description of the invention, a basic overview of conventional read channels, digital Viterbi detectors, and data recovery techniques follows.
Referring again to FIG. 1, the digital Viterbi detector 20 xe2x80x9crecoversxe2x80x9d the data stored on the disk 12 from the digitalized samples of the read signal generated by the read circuit 18. Specifically, the read head 16 reads data from the disk 12 in a serial manner. That is, assuming the stored data is binary data, the read head 16 senses one or more bits at a time as the surface of the disk 12 spins it, and generates a series of sense voltages that respectively correspond to the sensed bits. This series of sense voltages composes the read signal, which consequently represents these sensed data bits in the order in which the head 16 sensed them. Unfortunately, because the disk 12 spins relatively fast with respect to the read head 16, the read signal is not a clean logic signal having two distinct levels that respectively represent logic 1 and logic 0. Instead, the read signal is laden with noise and inter-symbol interference (ISI), and thus more closely resembles a continuous analog signal than a digital signal. Using the sample clock, which is generated with circuitry that is omitted from FIG. 1, the read circuit 18 samples the read signal at points that correspond to the read head 16 being aligned with respective bit storage locations on the surface of the disk 12. The read circuit 18 digitizes these samples, and from these digitized samples, the Viterbi detector 20 ideally generates a sequence of bit values that is the same as the sequence of bit values stored on the disk 12 as described below.
FIG. 2 is a block diagram of the Viterbi detector 20 of FIG. 1. The detector 20 receives the digitized read-signal samples from the read circuit 18 (FIG. 1) on an input terminal 22. A data-sequence-recovery circuit 24 processes these samples to identify the bits represented by the read signal and then provides these identified bits to shift registers 26, which reproduce the stored data sequence from these bits. The detector 20 then provides this reproduced data sequence on an output terminal 28 as the recovered data sequence.
For example purposes, the operation of the Viterbi detector 20 is discussed in conjunction with a Decode data-recovery protocol, it being understood that the concepts discussed here generally apply to other Viterbi detectors and other data-recovery protocols.
Assuming a noiseless read signal and binary stored data, the read circuit 18, which in this example is designed to implement the Decode protocol, generates ideal digitized read-signal samples B having three possible relative values: xe2x88x921, 0, and 1. These values represent respective voltage levels of the read signal, and are typically generated with a 6-bit analog-to-digital (A/D) converter. For example, according to one 6-bit convention, xe2x88x921=111111, 0=000000, and 1=011111. The value of the ideal sample B at the current sample time k, i.e., Bk, is related to the bit values of the stored data sequence according to the following equation:
Bk=Akxe2x88x92Akxe2x88x921xe2x80x83xe2x80x831)
Ak is the current bit of the stored data sequence, i.e., the bit that corresponds to the portion of the read signal sampled at the current sample time k. Likewise, Akxe2x88x921 is the immediately previous bit of the stored data sequence, i.e., the bit that corresponds to the portion of the read signal sampled at the immediately previous sample time kxe2x88x921. Table I includes a sample portion of a sequence of bit values A and the corresponding sequence of ideal samples B for sample times kxe2x88x92k+6.
Referring to Table I, Bk+1=Ak+1xe2x88x92Ak=1, Bk+2=Ak+2xe2x88x92Ak+1=0, and so on. Therefore, by keeping track of the immediately previous bits A, one can easily calculate the value of current bit A from the values of the immediately previous bit A and the current sample B. For example, by rearranging equation (1), we get the following:
Ak=Bk+Akxe2x88x921xe2x80x83xe2x80x832)
Equation (2) is useful because Bk and Akxe2x88x921 are known and Ak is not. That is, we can calculate the unknown value of bit Ak from the values of the current sample Bk and the previously calculated, and thus known, bit Akxe2x88x921. It is true that for the very first sample Bk there is no previously calculated value for Akxe2x88x921. But the values of Ak and Akxe2x88x921 can be determined from the first Bk that equals 1 or xe2x88x921, because for 1 and xe2x88x921 there is only one respective solution to equation (1). Therefore, a data sequence can begin with a start value of 010101 . . . to provide accurate initial values for Bk, Ak, and Akxe2x88x921.
Unfortunately, the read signal is virtually never noiseless, and thus the read circuit 18 generates non-ideal, i.e., noisy, digitized samples Z, which differ from the ideal samples B by respective noise components. Table II includes an example sequence of noisy samples Z that respectively corresponds to the ideal samples B and the bits A of Table 1.
For example, the difference between Zk and Bk equals a noise component of 0.1, and so on.
According to one technique, a maximum-likelihood detector (not shown) recovers the bits A of the stored data sequence by determining and then using the sequence of ideal samples B that is xe2x80x9cclosestxe2x80x9d to the sequence of noisy samples Z. The closest sequence of samples B is defined as being the shortest Euclidean distance xcex from the sequence of samples Z. Thus, for each possible sequence of samples B, the detector 20 calculates the respective distance xcex according to the following equation:             3      )        ⁢          xe2x80x83        ⁢    λ    =            ∑              y        =        k                    y        =                  k          +          n                      ⁢          xe2x80x83        ⁢                  (                              Z            y                    -                      B            y                          )            2      
For example, for the B and Z sequences of Table II, one gets:
xcex=(0.1xe2x88x920)2+(0.8xe2x88x921)2+(xe2x88x920.2xe2x88x920)2+(xe2x88x921.1xe2x88x92xe2x88x921)2+(1.2xe2x88x921)2+(xe2x88x920.9xe2x88x92xe2x88x921)2+(0.1xe2x88x920)2=0.16xe2x80x83xe2x80x834)
Referring again to Tables I and 11, there are seven samples B in each possible sequence of B samples. Because the bits A each have two possible values (0 and 1) and because the sequence of B samples is constrained by equations (1) and (2), there are 27 possible sequences of B samples (the sequence of B samples in Tables I and II is merely one of these possible sequences). Using equation (4), a maximum-likelihood detector should calculate 27 xcex values, one for each possible sequence of B samples. The sequence of B samples that generates the smallest xcex value is the closest to the generated sequence of Z samples. Once the maximum-likelihood detector identifies the closest sequence of B samples, it uses these B samples in conjunction with equation (2) to recover the bits A of the stored data sequence.
Unfortunately, because most sequences of Z samples, and thus the corresponding sequences of B samples, include hundreds or thousands of samples, this maximum-likelihood technique is typically too computationally complex and time consuming to be implemented in a practical manner. For example, for a relatively short data sequence having one thousand data bits A, i=999 in equation (3) such that the Z sequence includes 1000 Z samples and there are 21000 possible B sequences that each include 1000 B samples. Therefore, using equation (3), the maximum-likelihood detector would have to calculate 21000 values for xcex, each of these calculations involving 1000 Z samples and 1000 B samples! Consequently, the circuit complexity and time required to perform these calculations would likely make the circuitry for a maximum-likelihood detector too big, too expensive, or too slow for use in a conventional disk drive.
Therefore, referring to FIGS. 3-11, the Viterbi detector 20 (FIG. 2) implements a technique called dynamic programming to identify the sequence of ideal B samples that is closest to the sequence of actual Z samples. Dynamic programming is less computationally intensive than the above-described technique because it experiences only a linear increase in processing complexity and time as the length of the data stream grows. Conversely, the above-described technique experiences an exponential increase in processing complexity and time as the length of the data stream grows.
Referring to FIG. 3, dynamic programming is best explained using a trellis diagram 30, which represents a detection algorithm that the Viterbi detector 20 executes. The trellis 30 includes possible data-stream states S0-S3 at Z sample times kxe2x88x92k+n, and for example purposes is constructed for the Viterbi detector 20 operating according to A Decode data-recover protocol, it being understood that trellises for other data-recovery protocols have similar characteristics. Also, one should understand that the trellis 30 is not a physical circuit or device. It is merely a state diagram that illustrates the operation of the Viterbi detector 20 as it implements dynamic programming according to A Decode data-recovery protocol.
As illustrated by the trellis 30, at any particular Z sample time kxe2x88x92k+n, the two most recent bits A and Axe2x88x921 of the binary data sequence have one of four possible states S: S0=00, S1=01, S2=10, and S3=11. Therefore, the trellis 30 includes one column of state circles 32 for each respective sample time kxe2x88x92k+n. Within each circle 32, the right-most bit 34 represents a possible value for the most recent bit A of the data sequence at the respective sample time, and the left-most bit 36 represents a possible value for the second most recent bit A. For example, in the circle 32b, the bit 34b represents a possible value (logic 1) for the most recent bit A of the data sequence at sample time k, i.e., Ak, and the bit 34b represents a possible value (logic 0) for the second most recent bit Akxe2x88x921. Each circle 32 includes possible values for the most recent and second most recent bits A and Axe2x88x921, respectively, because according to equation (1), B depends on the values of the most recent bit A and the second most recent bit Axe2x88x921. Therefore, the Viterbi detector 20 can calculate the respective B sample for each circle 32 from the possible data values A and Axe2x88x921 within the circle.
Also as illustrated by the trellis 30, only a finite number of potential state transitions exist between the states S at one sample time kxe2x88x92k+n and the states S at the next respective sample time k+1xe2x88x92k+n+1. xe2x80x9cBranchesxe2x80x9d 38 and 40 represent these possible state transitions. Specifically, each branch 38 points to a state having logic 0 as the value of the most recent data bit A, and each branch 40 points to a state having logic 1 as the value of the most recent data bit A. For example, if at sample time k the state is S0 (circle 32a) and the possible value of the next data bit Ak+1 is logic 0, then the only choice for the next state S at k+1 is S0 (circle 32e). Thus, the branch 38a represents this possible state transition. Likewise, if at sample time k the state is S0 (circle 32a) and possible value of the next data bit Ak+1 is logic 1, then the only choice for the next state S at k+1 is S1 (circle 32f). Thus, the branch 40a represents this possible state transition. Furthermore, the value 42 represents the value of the next data bit A1 pointed to by the respective branch 38 or 40, and the value 44 represents the value of B that the next data bit A1 and equation (1) give. For example, the value 42c (logic 0) represents that the branch 38b points to logic 0 as the possible value of the next data bit Ak+1, and the value 44c (xe2x88x921) represents that for the branch 38b, equation (1) gives Bk+1=0(Ak+1)xe2x88x921(Ak)=xe2x88x921.
In addition, the trellis 30 illustrates that for the sequence of bits A, the state transitions xe2x80x9cfully connectxe2x80x9d the states S at each sampling time to the states S at each respective immediately following sample time. In terms of the trellis 30, fully connected means that at each sampling time kxe2x88x92k+n, each state S0-S3xe2x80x2 has two respective branches 38 and 40 entering and two respective branches 38 and 40 leaving. Therefore, the trellis 30 is often called a fully connected trellis.
Furthermore, the trellis 30 illustrates that the pattern of state transitions between adjacent sample times is time invariant because it never changes. In terms of the trellis 30, time invariant means that the pattern of branches 38 and 40 between states at consecutive sample times is the same regardless of the sampling times. That is, the branch pattern is independent of the sampling time. Therefore, the trellis is often called a fully connected trellis.
Still referring to FIG. 3, in operation, the Viterbi detector 20 calculates the xe2x80x9clengthsxe2x80x9d of the xe2x80x9cpathsxe2x80x9d through the trellis 30 and recovers the sequence of data bits A that corresponds to the xe2x80x9cshortestxe2x80x9d path. Each path is composed of respective serially connected branches 38 or 40, and the length xcex of each path (often called the path metric xcex) equals the sum of the lengths X of the branches (often called the branch metrics X) that compose the path. Each branch length X is represented by the following equation:
Xy=(Zyxe2x88x92By)2xe2x80x83xe2x80x835)
And each path length xcex is represented by the following equation:             6      )        ⁢          xe2x80x83        ⁢          λ      S        =            ∑              y        =        k                    y        =                  k          +          n                      ⁢          xe2x80x83        ⁢          X      y      
Thus, during each sampling period between the respective sample times kxe2x88x92k+n, the Viterbi detector 20 updates the respective length xcex of each path by adding the respective branch length X thereto. The path lengths xcex are actually the same values as given by equation (3) for the sequences of B samples represented by the paths through the trellis 30. But major differences between the closest-distance and dynamic-programming techniques are 1) dynamic programming updates each path length xcex once during each sample period instead of waiting until after the read circuit 18 has generated all of the samples Z, and 2) dynamic programming calculates and updates the path lengths xcex for only the surviving paths through the trellis 30 (one to each state S as discussed below), and thus calculates significantly fewer xcex values than the closest-distance technique. These differences, which are explained in more detail below, significantly reduce the processing complexity and time for data recovery as compared with the maximum-likelihood technique.
To minimize the number of trellis paths and path lengths xcex that it monitors, the Viterbi detector 20 monitors only the xe2x80x9csurvivingxe2x80x9d paths through the trellis 30 and updates and saves only the path lengths xcexs of these surviving paths. The surviving path to a possible state S at a particular sample time is the path having the shortest length xcexs. For example, each of the states S0-S3 of the trellis 30 typically has one respective surviving path at each sample time kxe2x88x92k+n. Therefore, the number of surviving paths, and thus the computational complexity per sample period, depends only on the number of possible states S and not on the length of the data sequence. Conversely, with the maximum-likelihood technique described above, the computational complexity per sample period depends heavily on the length of the data sequence. Thus, the computational complexity of the dynamic-programming technique increases linearly as the length of the data sequence increases, whereas the computational complexity of the closest-distance technique increases exponentially as the length of the data sequence increases. For example, referring to the 1000-bit data sequence discussed above in conjunction with FIG. 2, the Viterbi detector 20 updates only four path lengths xcexS0-xcexS3 (one for each state S0-S3) using dynamic programming as compared to 21000 path lengths xcex using the maximum-likelihood technique! If one increases the length of the data sequence by just one bit, the detector 20 continues to update only four path lengths xcexS0-xcexS3 using dynamic programming whereas the detector 20 must calculate twice as many path lengths xcexxe2x80x9421001=2xc3x9721000xe2x80x94using the maximum-likelihood technique!
Referring to FIGS. 4A-11, an example of the operation of the Viterbi detector 20 of FIG. 2 is discussed where the detector 20 uses dynamic programming to recover the data sequence A of Table II using the sequence of Z samples also of Table II. FIGS. 3A, 4A, . . . , and 11 show the trellis diagram 30 and the surviving paths at respective sample times kxe2x88x921xe2x88x92k+6, and FIGS. 3B, 4B, . . . , and 10B show the contents of four (one for each state S0-S3) shift registers Reg0xe2x88x92Reg3xe2x80x94these registers compose the shift register 26 of the detector 20xe2x80x94at the respective sample times. As discussed below, the surviving paths eventually converge such that the contents of the registers 26 are the same by the time the detector 20 provides the recovered data sequence on its output terminal 28.
Referring to FIG. 4A and Table II, the trellis 30 begins at sample time kxe2x88x921, which is a don""t-care state because the data sequence A actually begins at sample time k. During the sampling period t, which is the period between the sampling times kxe2x88x921 and k, the Viterbi detector 20 (FIG. 2) receives the sample Zk=0.1 on the input terminal 22. Next, the recovery circuit 24 of the detector 20 calculates the branch lengths Xk for each of the respective branches 38 and 40 in accordance with equation (5). To perform these calculations, the circuit 24 uses the B samples 44 that are associated with the branches 38 and 40 as shown in FIG. 3. Table III shows the components Zk and Bk and the resulting branch lengths Xk and path lengths xcexk of this calculation.
Because the branch lengths Xk between the states at sample times kxe2x88x921 and k are the first branch lengths calculated, xcexk=Xk for all branches. The path lengths xcexk from Table III label the respective branches in FIG. 4A for clarity.
Next, the recovery circuit 24 identifies the shortest path to each state at sample time k, i.e., the surviving paths. Referring to state S0 at sample time k, both incoming paths have lengths xcexk=0.01. Therefore, both paths technically survive. But for ease of calculation, the recovery circuit 24 arbitrarily eliminates the path originating from the highest state (S2 here) at time kxe2x88x921, i.e., the path along branch 38c. Alternatively, the recovery circuit 24 could eliminate the path along branch 38a instead. But as discussed below, the detector 20 recovers the proper data sequence regardless of the path that the circuit 24 eliminates. Similarly, referring to states S1-S3 at time k, both of their respective incoming paths have equal lengths xcexk, and thus the circuit 24 arbitrarily eliminates the path originating from the respective highest state. For clarity, the surviving paths are shown in solid line, and the eliminated paths are shown in dashed line.
Referring to FIG. 4B, once the Viterbi detector 20 identifies the surviving paths, the recovery circuit 24 loads the data bits A that compose the surviving paths into the respective shift registers Reg0-Reg3 of the shift register block 26 (FIG. 2). Reg0-Reg3 respectively correspond to the surviving paths ending at the states S0-S3. For example, referring to FIG. 4A, the recovery circuit 24 loads Ak=0 and Akxe2x88x921=0 into Reg0 because the surviving path, here branch 38a, connects bit 34a, which is Akxe2x88x921=0, with bit 34e, which is Ak=0. These bits are shifted into the left side of Reg0 such that they occupy the register locations indicated by the xe2x80x9cAkxe2x80x9d and xe2x80x9cAxe2x88x921xe2x80x9d legends above Reg0-Reg3. Thus, the most recent value, here Ak, always occupies the left most location of Reg0. Likewise, Ak and Akxe2x88x921 for the other surviving paths, here branches 40a, 38b, and 40b, are respectively shifted into Reg1-Reg3.
Referring to FIG. 5A, during the sampling period t+1 between the sample times k and k+1, the Viterbi detector 20 receives the sample Zk+1=0.8. Next, the recovery circuit 24 calculates the branch length Xk+1 for each of the respective branches 38 and 40 between k and k+1 in accordance with equation (5), and updates the previous surviving path lengths xcexk to get the new path lengths xcexkxe2x88x921 according to equation (6). To perform these calculations, the circuit 24 uses the B samples 44 that are associated with the branches 38 and 40 as shown in FIG. 3. Table IV shows the components Zk+1 and Bk+1 and the resulting branch lengths Xkxe2x88x921 and path lengths xcexkxe2x88x921 of this calculation.
The path lengths xcexk+1 from Table IV label the respective branches in FIG. 5A for clarity.
Next, the recovery circuit 24 identifies the shortest path to each state at time k+1, i.e., the surviving paths, which are shown in solid line in FIG. 5A. Referring to the state S0 at time k+1, the path that includes the branch 38e (xcexk+1=0.65) is shorter than the path that includes the branch 30g (xcexk+1=1.85). Therefore, the recovery circuit 24 eliminates the latter path, which is shown in dashed line, and updates the surviving path length xcexS0 for state S0 to equal to 0.65. Similarly, referring to the states S1-S3 at time k+1, the recovery circuit 24 eliminates the paths that include branches 40g, 38f, and 40f, respectively, and updates the surviving path lengths as follows: xcexS1=0.05, xcexS2=3.25, and xcexS3=0.65.
Referring to FIG. 5B, once the recovery circuit 24 identifies the surviving paths, it loads the data bits A that compose the surviving paths into the respective shift registers Reg0-Reg3. For example, referring to FIG. 5A, the recovery circuit 24 right shifts Ak+1=0 into Reg0 because the surviving path for S0, here the path that includes branches 38a and 38e, passes through S0 at k and kxe2x88x921 and thus includes bits 34a (Akxe2x88x921=0), 34e (Ak=0), and 34i (Ak+1=0). Conversely, because the surviving path for S1 now passes through S0 at time k, the circuit 24 right shifts Ak+1=1 into Reg1 and loads Ak=Akxe2x88x921=0 from Reg0 into Reg1. Thus, Reg1 now includes the bits A that compose the surviving path to S1 at time k+1. Likewise, because the surviving path for S2 now passes through S3 at time k, the circuit 24 right shifts Ak+1=0 into Reg2 and loads Ak=Akxe2x88x921=1 from Reg3 into Reg2. Thus, Reg2 now includes the bits A that compose the surviving path to S2 at time k+1. Furthermore, because the surviving path for S3 passes through S3 and k and S1 and kxe2x88x921, the recovery circuit 24 merely right shifts Ak+1=1 into Reg3.
Referring to FIG. 6A, during the sampling period t+2 between sample times k+1 and k+2, the Viterbi detector 20 receives a sample Zk+2=0.2. Next, the recovery circuit 24 calculates the branch lengths Xk+2 for the respective branches 38 and 40 in accordance with equation (5), and updates the surviving path lengths xcexkxe2x88x921 to get the new path lengths xcexk+2 according to equation (6). The new path lengths xcexk+2 label the respective branches originating from the states S at time k+1 for clarity.
Next, the recovery circuit 24 identifies the surviving paths to each state S at time k+2 in a manner similar to that discussed above in conjunction with FIG. 5A. The surviving paths are in solid line, the eliminated branches between k+1 and k+2 are in dashed line, and the previously eliminated branches are omitted for clarity. One can see that at time k, the surviving paths converge at S0. That is, all of the surviving paths to the states S at time k+2 pass through S0 at time k. Thus, the recovery circuit 24 has recovered Ak=0, which, referring to Table II, is the correct value for Ak in the data sequence A.
Referring to FIG. 6B, once the recovery circuit 24 identifies the surviving paths, it shifts or loads the data bits A that compose the surviving paths into the respective shift registers Reg0-Reg3 as discussed above in conjunction with FIG. 5B. For example, referring to FIG. 6A, the recovery circuit 24 merely right shifts Ak+2=0 into Reg0 because the surviving path to S0, here the path that includes branches 38a, 38e, and 38i, passes through S0 at times kxe2x88x921, k, and k+1 and thus includes bits 34a (Akxe2x88x921=0), 34e (Ak=0), 34i (Ak+1=0), and 34m (Ak+2=0). Likewise, the recovery circuit 24 shifts or loads the bits Ak+2, Akxe2x88x921, Ak, and Akxe2x88x921 that compose the other surviving paths into Reg1-Reg3. One can see that each of the locations Ak in Reg0-Reg3 stores the same value, here logic 0. This confirms the convergence of the surviving paths to S0 at time k as discussed above in conjunction with FIG. 6A. Therefore, it follows that when the Ak bits are shifted out of Reg0-Reg3, respectively, each bit Ak will equal logic 0, which is the recovered value of the bit Ak. Thus, the output terminal 28 (FIG. 2) of the Viterbi detector 20 can be connected to the right-shift output of any one of the registers Reg0-Reg3.
Referring to FIG. 7A, during the sampling period t+3 between the sample times k+2 and k+3, the Viterbi detector 20 receives the sample Zk+3=xe2x88x921.1. Next, the recovery circuit 24 calculates the branch lengths Xk+3 for the respective branches 38 and 40 in accordance with equation (5), and updates the path lengths xcexk+2 to get the new path lengths xcexk+3 according to equation (6). The new path lengths xcexk+3 label the respective branches originating from the states S at time k+2 for clarity.
Next, the recovery circuit 24 identifies the surviving paths (solid lines) to each state S at time k+3. One can see that each of the states S0 and S1 technically have two surviving paths because the path lengths xcexk+3 for these respective pairs of paths are equal (both xcexk+3=1.9 for S0 and both xcexk+3=5.1 for S1). Therefore, as discussed above in conjunction with FIGS. 4A and 4B, the recovery circuit 24 arbitrarily selects the respective paths that pass through the lowest state S at k+2 as the surviving paths for S0 and S1.
Referring to FIG. 7B, once the recovery circuit 24 identifies the surviving paths, it left shifts or loads the data bits A that compose the surviving paths into the respective shift registers Reg0-Reg3. For example, referring to FIG. 7A, the recovery circuit 24 right shifts Ak+3=0 into Reg0 because the surviving path to S0xe2x80x94here the arbitrarily selected path that includes branches 38a, 38e, 38l, and 38mxe2x80x94passes through S0 at times kxe2x88x921xe2x88x92k+2 and thus includes bits 34a (Akxe2x88x921=0), 34e (Ak=0), 34i (Ak+1=0), 34m (Ak+2=0), and 34q (Ak+3=0). Likewise, the recovery cir shifts or loads as appropriate the bits Ak+3, Ak+2, Akxe2x88x921, Ak, and Akxe2x88x921 of the other surviving paths into Reg1-Reg3.
Referring to FIG. 8A, during the sampling period t+4 between the sampling times k+3 and k+4, the Viterbi detector 20 receives a sample Zk+4=1.2. Next, the recovery circuit 24 calculates the branch length Xk+4 for each of the respective branches 38 and 40 in accordance with equation (5), and updates the path lengths xcexk+3 to generate the new path lengths xcexk+4 according to equation (6). The path lengths xcexk+4 label the respective branches originating from the states S at time k+3 for clarity.
Next, the recovery circuit 24 identifies the surviving paths to each state S at time k+4. One can see that at time k+1 the surviving paths converge at S1, and that at time k+2 the surviving paths converge at S3. Thus, in addition to bit Ak, the recovery circuit 24 has recovered Ak+1=1 and Ak+2=1, which, referring to Table II, are the correct values for the Ak+1 and Ak+2 bits of the data sequence A.
Referring to FIG. 8B, once the recovery circuit 24 identifies the surviving paths, it right shifts or loads the data bits A that compose the surviving paths into the respective shift registers Reg0-Reg3. For example, the recovery circuit 24 right shifts Ak+4=0 and loads Ak+2=Akxe2x88x921=1 from Reg3 into the respective locations of Reg0. Referring to FIG. 8A, the circuit 24 does this because the surviving path to S0 at k+4xe2x80x94here the path that includes the branches 38a, 40e, 40j, 38p, and 38sxe2x80x94passes through S2 at k+3, S3 at k+2, S1 at kxe2x88x921, and S0 at k and kxe2x88x921, and thus includes bits 34a (Akxe2x88x921=0), 34e (Ak=0), 34j (Ak+1=1), 34p (Ak+2=1), 34s (Ak+3=0), and 34u (Ak+4=0). Likewise, the recovery circuit 24 shifts or loads as appropriate the bits Ak+4, Ak+3, Ak+2, Ak+1, Ak, and Akxe2x88x921 of the other surviving paths into Reg1-Reg3, respectively. One can see that each of the bits Akxe2x88x921-Ak+2 in Reg0-Reg3 has the same respective value, here Akxe2x88x921=0, Ak=0, Ak+1=1, Ak+2=1. This confirms convergence of the surviving paths to S1 at time k+1 and to S3 at time k+2 as discussed above in conjunction with FIG. 8A.
Referring to FIG. 9A, during the sampling period t+5 between sample times k+4 and k+5, the Viterbi detector 20 receives a sample Zk+5=xe2x88x920.9. Next, the recovery circuit 24 calculates the branch length Xk+5 for each of the respective branches 38 and 40 in accordance with equation (5), and updates the path lengths xcexk+4 to generate the new path lengths xcexk+5 according to equation (6). The updated path lengths xcexk+5 label the respective branches originating from the states S at time k+4 for clarity.
Next, the recovery circuit 24 identifies the surviving paths to each state S at time k+5. One can see that at time k+3, the surviving paths converge at S2. Thus, in addition to bits Ak, Akxe2x88x921, and Ak+2, the recovery circuit 24 has recovered Ak+3=0, which, referring to Table II, is the correct value for the bit Ak+3 of the data sequence A.
Referring to FIG. 9B, once the recovery circuit 24 identifies the surviving paths, it right shifts or loads the data bits A that compose the surviving paths into the respective shift registers Reg0-Reg3. For example, the recovery circuit 24 right shifts Ak+5=0 into Reg0. The circuit 24 does this because referring to FIG. 9A, the surviving path to S0 at k+5xe2x80x94here the path that includes branches 38a, 40e, 40j, 38p, 38s, and 38uxe2x80x94passes through S0 at k+4, S2 at k+3, S3 at k+2, S1 at k+1, and S0 at k and kxe2x88x921 and thus includes bits 34a (Akxe2x88x921=0), 34e (Ak=0), 34j (Ak+1=1, 34p (Ak+2=1), 34s (Ak+3=0), 34u (Ak+4=0), and 34y (Ak+5=0). Likewise, the recovery circuit 24 shifts or loads as appropriate the bits Ak+5, Ak+4, Ak+3, Ak+2, Akxe2x88x921, Ak, and Akxe2x88x921 of the other surviving paths into Reg1-Reg3. One can see that the bits Akxe2x88x921-Ak+3 in Reg0-Reg3 are respectively the same, here Akxe2x88x921=0, Ak=0, Akxe2x88x921=1, Ak+2=1, and Ak+3=0. This confirms the convergence of the surviving paths to S2 at time k+3 as discussed above in conjunction with FIG. 9A.
Referring to FIG. 10A, during the sampling period t+6 between sample times k+5 and k+6, the Viterbi detector 20 receives a sample Zk+6=0.1. The recovery circuit 24 calculates the branch length Xk+6 for each of the respective branches 38 and 40 in accordance with equation (5), and updates the path lengths xcexk+5 to generate the new path lengths xcexk+6 according to equation (6). The updated path lengths xcexk+6 label the respective branches originating from the states S at time k+5 for clarity.
Next, the recovery circuit 24 identifies the surviving paths to each state S at time k+6. One can see that at time k+4, the surviving paths converge at S1. Thus, in addition to bits Ak-Ak+3, the recovery circuit 24 has recovered Ak+4=1, which referring to Table II, is the correct value for the bit Ak+4 of the data sequence A.
Referring to FIG. 10B, once the recovery circuit 24 identifies the surviving paths, it right shifts or loads the data bits A that compose the surviving paths into the respective shift registers Reg0-Reg3. For example, the recovery circuit 24 right shifts Ak+6=0 and loads Ak+4=1 from Reg2 into Reg0. The circuit 24 does this because referring to FIG. 10A, the surviving path to S0 at k+6xe2x80x94here the path that includes branches 38a, 40e, 40j, 38p, 40s, 38v, and 38aaxe2x80x94passes through S2 at k+5, S0 at k+4, S2 at k+3, S3 at k+2, S1 at k+1, and S0 at k and kxe2x88x921 and thus includes bits 34a (Akxe2x88x921=0), 34e (Ak32 0), 34j (Akxe2x88x921=1), 34p (Ak+2=1), 34s (Ak+3=0), 34v (Ak+4=1), 34aa (Ak+5=0), and 34cc (Ak+6=0). Likewise, the recovery circuit 24 shifts or loads as appropriate the bits Ak+6, Ak+5, Ak+4, Ak+3, Ak+2, Akxe2x88x921, Ak, and Akxe2x88x921 of the other surviving paths into Reg1-Reg3, respectively. One can see that the bits Akxe2x88x921-Ak+4 in Reg0-Reg3 are respectively the same, here Akxe2x88x921=0, Akxe2x88x921=0, Ak+0, Ak+1=1, Ak+2=1, Ak+3=0, and Ak+4=1. This confirms the convergence of the surviving paths to S1 at time k+4 as discussed above in conjunction with FIG. 10A.
FIG. 11 is the trellis diagram 30 of FIG. 10A showing only the surviving paths for clarity.
Referring again to FIGS. 4A-11, the latency of the Viterbi detector 20 of FIG. 2 is 4. Referring to FIGS. 7A-8B, the most samples Z that the detector 20 must process before times one must wait the surviving paths converge is 4. For example, the surviving paths do not converge at k+1, and thus the bit Ak+1 is not the same in all the registers Reg0-Reg3, until the sample time k+4. Therefore, the Viterbi detector 20 must process four samples Zk+1xe2x88x92Zk+4 before the bit Ak+1 is valid, i.e., before the value of the bit Ak+1 is the same in all of the registers Reg0-Reg3.
The Viterbi detector 20 continues to recover the remaining bits of the data sequence A in the same manner as described above in conjunction with FIGS. 4A-11. Because the detector 20 updates only 8 path lengths xcexk+6 and chooses only 4 surviving paths per sample period T regardless of the length of the data sequence A, the processing complexity and time increase linearly, not exponentially, with the length of the data sequence.
Although the trellis 30 is shown having four states S0-S3 to clearly illustrate the dynamic-programming technique, the Decode Viterbi detector 20 typically implements a trellis having two states, S0=0 and S1=1, to minimize the complexity of its circuitry.
In summary, the Viterbi detector 20 stores (in Reg0-Reg3) a respective history of each surviving path to a respective state (S) in a trellis diagram at least until all of the surviving paths converge into a single path that represents the recovered data sequence. More detailed information regarding the Viterbi detector 20 and other types of Viterbi detectors can be found in many references including xe2x80x9cDigital Baseband Transmission and Recording,xe2x80x9d by Jan W. M. Bergmans, Kluwer Academic Publishers 1996, which is incorporated by reference.
In one aspect of the invention, a Viterbi detector receives a signal that represents a sequence of values. The detector recovers the sequence from the signal by identifying surviving paths of potential sequence values and periodically eliminating the identified surviving paths having a predetermined parity.
By recognizing the parity of portions of a data sequence, such a Viterbi detector more accurately recovers data from a read signal having a reduced SNR and thus allows an increase in the storage density of a disk drive""s storage disk. Specifically, the Viterbi detector recovers only sequence portions having a recognized parity such as even parity and disregards sequence portions having unrecognized parities. If one encodes these sequence portions such that the disk stores them having the recognized parity, then an erroneously read word is more likely to have an unrecognized parity than it is to have the recognized parity. Therefore, by disregarding words that have unrecognized parities, the accuracy of such a Viterbi detector is considerably greater than the accuracy of prior Viterbi detectors, which cannot distinguish sequence portions based on parity. This greater accuracy allows the Viterbi detector to more accurately recover data from a read signal having a relatively low SNR, and thus allows the Viterbi detector to more accurately recover data from a disk having a relatively high storage density.